#include "Patricia.h"
#include "PatriciaNodo.h"

Patricia::Patricia()
{
	_raiz = NULL;
	_cardinal = 0;
}

Patricia::Patricia( const string& s )
{
	_raiz = NULL;
	_cardinal = 0;
}

Patricia::Patricia( const Patricia& pat )
{
	_raiz = NULL;
	_cardinal = 0;
	_copiar( pat._raiz, _raiz );
}

Patricia::~Patricia()
{
	_destruir( _raiz );
	_raiz = NULL;
	_cardinal = 0;
}

bool Patricia::operator==( const Patricia & pat ) const
{
	return 	( _raiz == NULL && pat._raiz == NULL ) 
			|| ( _raiz != NULL && pat._raiz != NULL && *_raiz == *pat._raiz );
}

bool Patricia::operator!=( const Patricia & pat ) const
{
	return(!(*this == pat)); 
}

Patricia& Patricia::operator=( const Patricia & pat )
{
	if(*this != pat)
	{
		_destruir(_raiz);
		_raiz = pat._raiz;
	}
	
    return *this;
}

void Patricia::agregar( const string& s )
{
	//si no tiene raiz
	if( _raiz == NULL )
	{
		_raiz = new PatriciaNodo();
	}
	
	//indice correspondiente a la clave
	string clave = s;
	int indice = _indice(s);
	
	//nodo
	PatriciaNodo *nodo = _raiz->getPatriciaNodoLetra(indice);
	
	//si no esta definido el nodo de la letra correspondiente
	if( nodo == NULL )
	{
		_raiz->setPatriciaNodoLetra( new PatriciaNodo( _raiz, clave ), indice );
	}
	//si el nodo esta definido
	else
	{
		//guarda
		bool agregado = false;
		//cadena auxiliar
		string claveNodo;
		//longitud de las cadenas por si es o(n)
		unsigned int lengthClaveNodo, lengthClave = clave.length();
		//contador
		unsigned int i;
		//padre
		PatriciaNodo *padre = _raiz;
		//nodos auxiliares
		PatriciaNodo *nodoIntermedio, *nodoHijo;
	
		//mientras no haya agregado el elemento
		while( !agregado )
		{
			//ya se que la primer letra coincide
			i = 1;
			//warning: aca estoy copiando una cadena
			claveNodo = nodo->getClave();
			//guardo el tamano de la clave
			lengthClaveNodo = claveNodo.length();
			
			//busco hasta que caracter coinciden
			while( i < lengthClaveNodo && i < lengthClave && clave[i] == claveNodo[i] )
				i++;
			
			//si tengo que partir la clave del nodo
			if( i < lengthClaveNodo )
			{
				//clave que tiene que quedar en el nodo intermedio
				string claveIntermedia = claveNodo;
				claveIntermedia.erase( i, lengthClaveNodo );
				
				//nodo intermedio
				nodoIntermedio = new PatriciaNodo( padre, claveIntermedia );
				
				//agrego el nodo intermedio al padre
				padre->setPatriciaNodoLetra( nodoIntermedio, _indice(claveIntermedia) );
				
				//hay que cambiarle la clave al nodo actual
				claveNodo.erase( 0, i );
				lengthClaveNodo-= i;
				
				//actualizo la clave del nodo
				nodo->setClave(claveNodo);
				//actualizo el padre del nodo
				nodo->setPatriciaNodoPadre(nodoIntermedio);
				//agrego el nodo actual al intermedio
				nodoIntermedio->setPatriciaNodoLetra( nodo, _indice(claveNodo) );
				
				//hay que sacarle a la clave nueva los caracteres q coinciden
				clave.erase( 0, i );
				lengthClave-= i;
				
				//agrego el nodo actual al intermedio
				nodoIntermedio->setPatriciaNodoLetra( new PatriciaNodo( nodoIntermedio, clave ), _indice(clave) );
				
				//agregue el elemento
				agregado = true;
			}
			//si coinciden en todas las letras del nodo
			else if( i == lengthClaveNodo && i < lengthClave )
			{
				//le saco a la clave original lo que ya recorri
				clave.erase( 0, i );
				lengthClave-= i;
				
				//obtengo el nodo hijo correspondiente
				nodoHijo = nodo->getPatriciaNodoLetra( _indice(clave) );
				
				//si el nodo hijo no existe
				if( nodoHijo == NULL )
				{
					nodo->setPatriciaNodoLetra( new PatriciaNodo( nodo, clave ), _indice(clave) );
					
					//agregue el elemento
					agregado = true;
				}
				//si el nodo existe
				else
				{
					//el padre es el nodo actual
					padre = nodo;
					//el nodo que tengo que revisar es el nodo hijo
					nodo = nodoHijo;
				}
			}
		}
	}
	
	//indico que agregue el elemento
	_cardinal++;
}

bool Patricia::pertenece( const string& s ) const
{
	//indice correspondiente a la clave
	int indice = _indice(s);
	string clave = s;
    //cadena auxiliar
    string claveNodo;
    //longitud de las cadenas por si es o(n)
    unsigned int lengthClaveNodo, lengthClave = clave.length();
    //contador
    unsigned int i;
    //nodos auxiliares
    PatriciaNodo *nodo;
	//padre
	PatriciaNodo *padre = _raiz;
	
	//mientras tenga padre
	while( padre != NULL )
	{
		nodo = padre->getPatriciaNodoLetra(indice);
		
		//si esta definida
		if( nodo != NULL )
		{
			//ya se que la primer letra coincide
			i = 1;
			
			claveNodo = nodo->getClave();
			lengthClaveNodo = claveNodo.length();
			
			//busco hasta que caracter coinciden
			while( i < lengthClaveNodo && i < lengthClave && clave[i] == claveNodo[i] )
				i++;
				
			//si coinciden en todas las letras del nodo
			//y todavia me sobra clave
			//y el nodo tiene hijos
			if( i == lengthClaveNodo && i < lengthClave && nodo->tieneHijos() )
			{
				//le saco a la clave que busco lo que ya recorri
				clave.erase( 0, i );
				lengthClave-= i;
				
				//voy al nodo correspondiente
				nodo = nodo->getPatriciaNodoLetra( _indice(clave) );
				
				//si el nodo existe
				if( nodo != NULL )
				{
                    claveNodo = nodo->getClave();
        			lengthClaveNodo = claveNodo.length();
        			
					//si es una hoja
					if( !nodo->tieneHijos() )
					{
						//comparo el resto de la clave
						return claveNodo == clave;
					}
					//si no es una hoja
					else
					{
						//sigo en el nodo hijo
						padre = nodo;
						
						//con el resto de la clave que busco
						clave.erase( 0, lengthClaveNodo );
						lengthClave-= lengthClaveNodo;
						
						//si todavia queda clave
						if( clave != "" )
							indice = _indice(clave);
						//si no quedaba solo una letra
						else
							return false;
					}
				}
				//si el nodo no existe no tengo por donde seguir
				else
				{
                    return false;
                }
			}
			//si coinciden en todas las letras ambas claves
			else if( i == lengthClaveNodo && i == lengthClave )
			{
				return !nodo->tieneHijos();
			}
			//si se me termino la clave del nodo y me sobra clave pero el nodo es una hoja
			//o si la clave se me termino y la del nodo no
			else
			{
				return false;
			}
		}
		//si no existe el nodo
		else
		{
			return false;
		}
	}
	
	return false;
}

void Patricia::sacar( const string& s )
{
	const char *c_clave = s.c_str();
	//indice correspondiente a la clave
	int indice = _indice(s);
	string clave = s;
		
	//padre
	PatriciaNodo *padre = _raiz;
	//nodo buscado
	PatriciaNodo *buscado = NULL;
	//nodos auxiliares
	PatriciaNodo *nodo;
    //cadena auxiliar
    string claveNodo;
    
    //longitud de las cadenas por si es o(n)
    unsigned int lengthClaveNodo, lengthClave = clave.length();
	
	//contador
	unsigned int i;
	
	//flag para saber si ya no es posible enontrar algo
	bool existe = true;
	
	//mientras no haya encontrado el nodo que quiero buscar
	while( buscado == NULL && existe )
	{
		nodo = padre->getPatriciaNodoLetra(indice);
		
		//si esta definida
		if( nodo != NULL )
		{
			//ya se que la primer letra coincide
			i = 1;
			
			claveNodo = nodo->getClave();
			lengthClaveNodo = claveNodo.length();
			
			//busco hasta que caracter coinciden
			while( i < lengthClaveNodo && i < lengthClave && clave[i] == claveNodo[i] )
				i++;
				
			//si coinciden en todas las letras del nodo
			//y todavia me sobra clave
			//y el nodo tiene hijos
			if( i == lengthClaveNodo && i < lengthClave && nodo->tieneHijos() )
			{
				//le saco a la clave que busco lo que ya recorri
				clave.erase( 0, i );
				lengthClave-= i;
				
				//guardo al padre
				padre = nodo;
				
				//voy al nodo correspondiente
				nodo = nodo->getPatriciaNodoLetra( _indice(clave) );
				
				//si el nodo existe
				if( nodo != NULL )
				{
                    claveNodo = nodo->getClave();
        			lengthClaveNodo = claveNodo.length();
        			
					//si es una hoja
					if( !nodo->tieneHijos() )
					{
						//comparo el resto de la clave
						if( claveNodo == clave )
							buscado = nodo;
					}
					//si no es una hoja
					else
					{
						//sigo en el nodo hijo
						padre = nodo;
						
						//con el resto de la clave que busco
						clave.erase( 0, lengthClaveNodo );
						lengthClave-= lengthClaveNodo;
						
						//si todavia queda clave
						if( clave != "" )
							indice = _indice(clave);
						//si no quedaba solo una letra
						else
							existe = false;
					}
				}
			}
			//si coinciden en todas las letras ambas claves
			else if( i == lengthClaveNodo && i == lengthClave )
			{
				if( !nodo->tieneHijos() )
					buscado = nodo;
			}
			//si se me termino la clave del nodo y me sobra clave pero el nodo es una hoja
			//o si la clave se me termino y la del nodo no
			else
			{
				existe = false;
			}
		}
	}
	
	//si encontro el nodo
	if( buscado != NULL )
	{
		//si el padre es la raiz o tiene mas de 2 hijos
		if( padre == _raiz || padre->cantidadHijos() > 2 )
		{
			//saco al buscado del padre
			padre->setPatriciaNodoLetra( NULL, _indice( buscado->getClave() ) );
			
			//borro el buscado
			_destruir(buscado);
			_cardinal--;
		}
		//si el padre no es la raiz y tiene dos hijos
		else if( padre->cantidadHijos() == 2 )
		{
			//busco al otro hijo
			PatriciaNodo *hermano = NULL;
			
			for
			(
				int l = 0;
				l < PatriciaNodo::LETRAS
					&& ( hermano == NULL || hermano == buscado );
				l++
			){
				hermano = padre->getPatriciaNodoLetra(l);
			}
			
			//saco la referencia del padre al hermano
   			padre->setPatriciaNodoLetra( NULL, _indice( hermano->getClave() ) );
			
			//junto la clave del hermano con el padre
			clave = padre->getClave() + hermano->getClave();
			//le doy la clave completa al hermano
			hermano->setClave( clave );
			//pongo al hermano en el lugar del padre
			//no uso directamente al padre
			//ya que el hermano podria no ser una hoja
			PatriciaNodo *abuelo = padre->getPatriciaNodoPadre();
			abuelo->setPatriciaNodoLetra( hermano, _indice(clave) );
			//actualizo el padre del hermano
			hermano->setPatriciaNodoPadre(abuelo);
			
			//borro al padre (y borra al buscado)
			_destruir(padre);
			//solo borre una hoja, la hoja "buscada"
            //su padre era un nodo "intermedio"
			_cardinal--;
		}
	}
}

int Patricia::cardinal() const
{
	return _cardinal;
}

int Patricia::_indice( const string& s ) const
{	
	int i = s[0] - 97;
	
	assert( i >= 0 && i < PatriciaNodo::LETRAS );
	
	return i;
}

void Patricia::_copiar( PatriciaNodo * nodoOrigen, PatriciaNodo * nodoDestino )
{
	//si hay nodo de origen
	if( nodoOrigen != NULL )
	{
		PatriciaNodo *nodoDestinoTmp, *nodoHijoOrigen, *nodoHijoDestino;
		
		//si hay nodo de destino
		if( nodoDestino != NULL )
		{
			nodoDestinoTmp = nodoDestino;
		}
		//si hay _raiz la tomo como nodo destino
		else if( _raiz != NULL )
		{
			nodoDestinoTmp = _raiz;
		}
		//si no hay _raiz creo un nodo vacio y lo uso de _raiz y destino 
		else
		{
			_raiz = new PatriciaNodo();
			nodoDestinoTmp = _raiz; 
		}
		
		//defino clave en el nodo destino
		nodoDestinoTmp->setClave( nodoOrigen->getClave() );
		
		//por cada nodo hijo del nodo origen
		for( int i = 0; i < PatriciaNodo::LETRAS; i++ )
		{
			//obtengo un nodo hijo del nodo origen
			nodoHijoOrigen = nodoOrigen->getPatriciaNodoLetra(i);
			
			//si esta definido el nodo hijo del nodo origen
			if( nodoHijoOrigen != NULL )
			{
				//creo un nodo hijo para el nodo destino
				nodoHijoDestino = new PatriciaNodo( nodoDestinoTmp, nodoHijoOrigen->getClave() );
				//lo defino en el nodo destino
				nodoDestinoTmp->setPatriciaNodoLetra( nodoHijoDestino, _indice( nodoHijoDestino->getClave() ) );
				//copio los nodos hijos de este nodo hijo
				_copiar( nodoHijoOrigen, nodoHijoDestino );
			}
		}
	}
}

void Patricia::_destruir( PatriciaNodo *nod )
{       
    if ( nod != NULL )
    {
    	int index = 0;
    	int letras = PatriciaNodo::LETRAS;
    	
        while( index < letras && nod->tieneHijos() )
        {   
            if ( nod->getPatriciaNodoLetra(index) != NULL )
            {
                _destruir( nod->getPatriciaNodoLetra(index) );
                nod->setPatriciaNodoLetra( NULL, index );
            }
            
            index++;
	    }
	    
        delete nod;
    }
}

ostream& operator<<( ostream& os, const Patricia& pat )
{
	
	os << *pat._raiz;
	
	return os;
}
